/**
 *
 * Titre du TP : TP2
 *
 * Nom  : NGUYEN
 * Prenom : Quang Hoang
 *
 * Remarques :
 */
#include <stdio.h>
#include <stdlib.h>
#include <sys/sysinfo.h>

#define MAX(a,b) ({ typeof (a) _a = (a); typeof (b) _b = (b); _a > _b ? _a : _b; })
#define MIN(a,b) ({ typeof (a) _a = (a); typeof (b) _b = (b); _a < _b ? _a : _b; })

typedef struct{
	long root;
	long size;
} subGraph_t; // pour tracing

struct sysinfo myinfo;

long getFreeRam(){
	  sysinfo(&myinfo);
//	  printf("freeram: %ld\n", myinfo.freeram/1024);
	  return myinfo.freeram;
}

static long * pere;

long trouver_racine(long v){
    if(pere[v] != v){
    	pere[v] = trouver_racine(pere[v]);
    }
    return pere[v];
}

void reunir(long v1, long v2){
    long r1 = trouver_racine(v1);
    long r2 = trouver_racine(v2);
    if( r1 != r2 ){
    	long child = MAX(r1,r2);
    	long parent = MIN(r1,r2);
    	pere[child] = parent;
    }
}

int sort(const void *x, const void *y) {
  return (*(int*)x - *(int*)y);
}

int main(int argc, char** argv){

	long ramBefore = getFreeRam();

	// check for nbr of arguments passed
	if(argc < 2){
		printf("Too few arguments!\n");
		exit(1);
	}

	FILE *f = fopen(argv[1], "r");

	long u = 0;
	long v = 0;
	long i = 0;

	long N = atol(argv[2]); //number of nodes

	pere = malloc(N * sizeof(long));

	// Init
	for(v=0 ; v<N; v++){
		pere[v] = v;
	}

	// Parcourir tous les aretes (u,v)
	while(!feof(f)){
		i++;
		fscanf(f, "%ld %ld", &u, &v);
		reunir(u,v);
	}
	fclose(f);

/*
	printf("Before refinement: ");
	for(i=0; i<N; i++){
		printf("%ld ", pere[i]);
	}
*/
	// Refinement
	for(i=0; i<N; i++){
		trouver_racine(i);
	}
/*
	printf("\nAfter  refinement: ");
	for(i=0; i<N; i++){
		printf("%ld ", pere[i]);
	}
*/

	// Traiter pere[] pour compter le nbr. composantes
	qsort(pere, N, sizeof(long), sort);

/*
	printf("\nAfter qsort : ");
	for(i=0; i<N; i++){
		printf("%ld ", pere[i]);
	}
*/

	long currentRoot = pere[0];
	long numSubGraph = 1; // Il existe tjrs au moins 1 composante

	for(i=0; i<N; i++){
		if(pere[i] != currentRoot){
			currentRoot = pere[i];
			numSubGraph++;
		}
	}
	printf("Nombre de composantes connexees: %ld\n", numSubGraph);
	printf("Leur taille moyenne: %4.2f\n", (float)N / (float)numSubGraph);

	//-------------- 3 max composantes ----------------//
	// init
	subGraph_t * composante = malloc(numSubGraph * sizeof(subGraph_t)); // pour tracing
	for(i=0; i<numSubGraph; i++){
		composante[i].size = 0;
	}

	currentRoot = pere[0];
	long index = 0;
	int * compSize = malloc(numSubGraph * sizeof(int)); // tableau de taille des composantes
	for(i=0 ; i<numSubGraph ; i++){
		compSize[i] = 0;
	}
	composante[index].root = currentRoot;

	//re-parcourir pere[]
	for(i=0; i<N; i++){
		if(pere[i] != currentRoot){
			currentRoot = pere[i];
			index++;
			composante[index].root = currentRoot;
		}
		composante[index].size++;
		compSize[index]++;
	}

/*
	for(i=0; i<numSubGraph; i++){
		printf("composante[%ld]  root:%ld  size:%ld\n", i, composante[i].root, composante[i].size);
	}
*/

	qsort(compSize, numSubGraph, sizeof(int), sort);

	printf("Taille des 3 composantes les plus grosses: ");

	for(i=numSubGraph-1; i>numSubGraph-4; i--){
		printf("%d ",compSize[i]);
	}
	printf("\n");

	long ramAfter = getFreeRam();

	printf("Memoire utilisee: %ld MB\n", (ramBefore - ramAfter)/1024/1024);

	free(pere);
	free(compSize);
	free(composante);

	return 0;
}

